package com.MSB2.sort1;

/**
 * 求数组中有多少逆序对
 * 4  3  1  0  6  2  3  1
 * 6 + 4 + 1 + 3 + 1 + 1
 * 16
 */
public class ReverseOrder {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 1, 0, 6, 2, 3, 1};
        int sum = pairSum(arr);
        System.out.println(sum);
    }

    public static int pairSum(int[] arr){
        if (arr == null || arr.length < 2){
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    public static int process(int[] arr, int L, int R){
        if (L == R)
            return 0;
        int mid = L + ((R - L) >> 1);
        int num1 = process(arr, L, mid);
        int num2 = process(arr, mid + 1, R);
        int num3 = merge(arr, L, mid, R);
        return num1 + num2 + num3;
    }

    /**
     * 合并两个排好序的数组
     * @param arr 数组
     * @param l 左
     * @param mid 中
     * @param r 右
     */
    private static int merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int sum = 0;
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r){
//            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
            if(arr[p1] <= arr[p2]){
                sum += (p2 - mid - 1);
                help[i++] = arr[p1++];
            }else {
                help[i++] = arr[p2++];
            }
        }
        while (p1 <= mid){
            sum += (r - mid );
            help[i++] = arr[p1++];
        }
        while (p2 <= r){
            help[i++] = arr[p2++];
        }
        System.arraycopy(help, 0, arr, l, help.length);
        return sum;
    }
}
